package cn.xkai.exercise.a;

import com.google.gson.Gson;

import java.util.Arrays;

/**
 * @description: 加一
 * 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
 * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
 * 你可以假设除了整数 0 之外，这个整数不会以零开头。
 * 1 <= digits.length <= 100
 * 0 <= digits[i] <= 9
 *
 * 自己的思路：根据题面意思直接转换成数字加1，然后再分别转换为数组(时间复杂度O(n)、空间复杂度O(n))
 *      优化版：计算末位数加1，然后判断是否进位（可能是因为填充0问题导致内存增多）(时间复杂度O(n)、空间复杂度接近O(1))
 * 借鉴的思路：同理优化版，代码逻辑更简介(时间复杂度O(n)、空间复杂度接近O(1))
 * @author: kaixiang
 * @date: 2022-07-04
 **/
public class Solution28 {
    public int[] plusOne(int[] digits) {
        StringBuilder sb = new StringBuilder();
        for (int digit : digits) {
            sb.append(digit);
        }
        int sum = Integer.parseInt(sb.toString()) + 1;
        String nums = String.valueOf(sum);
        if (nums.length() > digits.length) {
            digits = new int[nums.length()];
        }
        for (int i = 0; i < nums.length(); i++) {
            digits[i] = Integer.parseInt(nums.substring(i, i + 1));
        }
        return digits;
    }

    public int[] plusOneSweep(int[] digits) {
        int len = digits.length;
        for (int i = len - 1; i >= 0; i--) {
            if (digits[i] == 9) {
                digits[i] = 0;
                continue;
            }
            digits[i] += 1;
            break;
        }
        if (digits[0] == 0) {
            // 极端情况，数组都是9，故经过计算后原数组第一个肯定是0
            // 此时需要扩展数组，新数组肯定是1开头，其他都为0
            digits = new int[digits.length + 1];
            Arrays.fill(digits, 0);
            digits[0] = 1;
        }
        return digits;
    }

    public int[] plusOneRefer(int[] digits) {
        int len = digits.length;
        for (int i = len - 1; i >= 0; i--) {
            if (digits[i] != 9) {
                digits[i] += 1;
                break;
            }
            digits[i] = 0;
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }

    public static void main(String[] args) {
        int[] digits = {9, 9};
        Solution28 solution28 = new Solution28();
        System.out.println(new Gson().toJson(solution28.plusOneSweep(digits)));
    }
}
